Retrieving all vertices connected to a given vertex.
- Using an Adjacency List, we simply retrieve the list or set associated with vertex `u`. This operation is highly efficient for sparse graphs, with a cost proportional to the number of neighbors, $O(\deg(u))$.
- For an Adjacency Matrix, we must scan the entire row corresponding to vertex `u` and collect the indices where the value is non-zero. This always takes time proportional to the total number of vertices, $O(n)$.
Python: Neighbor Listing Functions
def neighbors_list(adj,u):
return sorted(adj[u])
def neighbors_matrix(A,i):
return [j for j,val in enumerate(A[i]) if val]